/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/coin-change-2
   @Language: C++
   @Datetime: 19-06-04 15:07
   */


class Solution {
public:
	/**
	 * @param amount: a total amount of money amount
	 * @param coins: the denomination of each coin
	 * @return: the number of combinations that make up the amount
	 */
	int change(int amount, vector<int> &coins) {
		// write your code here
		vector<int> dp(amount+1,0);
		dp[0]=1;
		for(int i=0; i<coins.size(); ++i)
			for(int j=1; j<=amount; ++j)
				if(j>=coins[i]) dp[j]+=dp[j-coins[i]];
		return dp[amount];
	}
};
